package 动态规划专项训练.动态规划训练1;

/**91.解码方法
 * 划分型动态规划
 * @author zx
 * @create 2022-03-30 20:35
 */
public class Num91 {
    public int numDecodings(String s) {
        //如果不变成数组,所有的(i - 1)要写成s.charAt(i - 1)
        char[] sc = s.toCharArray();
        int n = sc.length;
        if(n == 0){
            return 0;
        }
        //数组长度：n + 1(这样会很好处理)
        int[] f = new int[n + 1];
        f[0] = 1;
        //i: 前i个字母
        for(int i = 1;i <= n;i++){
            f[i] = 0;
            //last digit
            //前(i - 1)个字符的解码方式
            int t = sc[i - 1] - '0';
            if(t >= 1 && t <= 9){
                f[i] += f[i - 1];
            }
            //i的长度必须大于1
            if(i >= 2){
                //last two digits
                //前(i - 2)个字符的解码方式
                t = (sc[i - 2] - '0') * 10 + (sc[i - 1] - '0');
                if(t >= 10 && t <= 26){
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
}
